package leetcode.algorithm.dynamicPlan;

import lombok.Data;
import lombok.extern.slf4j.Slf4j;
import org.springframework.jdbc.core.JdbcTemplate;

import java.text.Collator;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Predicate;
import java.util.stream.Collectors;

import static java.lang.Math.random;

class JTempDemo {


    private JdbcTemplate jdbcTemplate;


    public void show() {

//        String sql = "insert into blog values(?,?,?)";
//        String sql  = "select * from table";
//        jdbcTemplate.execute(sql);
//        jdbcTemplate.update(sql,
//                new Object[]{blog.getId(), blog.getName(), blog.getUr()},
//                new int[]{java.sql.Types.INTEGER, java.sql.Types.VARCHAR, java.sql.Types.VARCHAR});



    }
}


class DemoOne12345 {

    public static void main(String[] args) {
        Object object = new Object();
        ThreadImpl thread = new ThreadImpl(object);
        ThreadImpl thread1 = new ThreadImpl(object);
        //  开启一个线程
        thread1.start();
        thread.start();
    }
}

//直接调用wait()方法，此时实际上是this.wait()，实际调用者为ThreadImp的实例对象thread。
// 而在修改后的代码中，wait()方法的调用者为lock。
class ThreadImpl extends Thread {

    //  线程锁对象
    private Object lock;

    public ThreadImpl(Object lock) {
        this.lock = lock;
    }

    //  重写线程的run方法，线程的业务执行逻辑
    @Override
    public void run() {

        synchronized (this) {

            //	执行一个for循环，打印0~9之间的数字
            for (int i = 0; i < 10; i++) {
                System.out.println(Thread.currentThread().getName() + "当前数字为：" + i);
            }

            try {
                /**	调用wait方法控制线程
                    如果是this.wait说明线程本身并没有

                 调用object的wait方法，是指，你的锁对象object在管理这些线程，因此在调用过程中，
                 调用这应该是object对象，就是你的说对象
                */
                this.wait(1000);
                this.notifyAll();
            } catch (Exception e) {
                System.out.println(e);
                e.printStackTrace();
            }finally {

                this.interrupt();
            }

        }
    }
}

class TestDemp{
    public static void main(String[] args) throws InterruptedException {
        Object object = new Object();
        SolutionTempDempOne1 s = new SolutionTempDempOne1(object);
        String[] str = {"有什么不一样？", "确实不一样", "对的", "都会有的","智能检测中。。。。。"};
        String ss = "对对对";
        for (int i = 0; i < 100; i++) {
            if(i<20){
                if(i<str.length){
                    ss = str[i];
                }
                if(i%2!=0){
                    ss =   ss;
                    System.out.println("safdsdafsafsfsafssafdsdafsafs"+ "fsafssafdsdafsafsfsasfsafssafdsdafsafsfsafs");
                }else{
                    System.out.println(Thread.currentThread().getName() + "safdsdafsafsfsafdsdafsafsfsafssafdsdafsafsfsafs");
                }

            }else {
                ss = "检测失败，最终还是消失了";
            }
            s.sy("result " + i + ": "+ ss);
        }
    }
}


class SolutionTempDempOne1 {


    private Object object;

    public SolutionTempDempOne1(Object object){

        this.object = object;
    }



    public synchronized void sy(String ss) throws InterruptedException {

        try{
            this.wait(400);
            System.out.println(ss);
        }catch (Exception e){
            System.out.println(e);
        }finally {

        }

    }

}


class SolutionTempDempOne{

    Object object = new Object();
    public static void main(String[] args) throws InterruptedException {
        double d = 1.3242342;
        String.valueOf(d);

        Double dd = 2.3;
        String.valueOf(dd);
        float f = 1.32344435323f;
        System.out.println(dd + "   " + f);
        SolutionTempDempOne s = new SolutionTempDempOne();
        System.out.println("value " + s.getNum());
    }

    public synchronized int getNum() throws InterruptedException {

/*        try{
            this.wait(1000);
            Thread.sleep(100);
        }catch (Exception e){

        }finally {
            this.notify();
        }*/
        new Thread(()->{
            try {
                object.wait(3000);
                object.notify();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }finally {
                System.out.println(Thread.currentThread() + "hihihi");

            }

        }).start();

        new Thread(()->{
            System.out.println(Thread.currentThread().getName() + "curName");
            try {
                Thread.sleep(3000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }).start();


        try{
            return 0;
        }finally {
            return 1;
        }


    }

}




class SolutionWeekOne {

    List<Integer> relist = new ArrayList<>();
    List<List<Integer>> relistALL = new ArrayList<>();

    public static void main(String[] args) {
        SolutionWeekOne s = new SolutionWeekOne();
        int[] nums1 = {13014,18206,602,18280,13698,7402,4506,6074,18272,7359},
                nums2 = {13014,6074,18206,13698,602,7402,18280,18272,7359,4506};
        s.advantageCount(nums1,nums2);
    }
    public int[] advantageCount(int[] nums1, int[] nums2) {
        boolean[] isUsed = new boolean[nums1.length];
        List<Integer> list = new ArrayList<>();
        recursion(isUsed, nums1, nums2, list, 0);
        int[] res = new int[nums1.length];
        for(int i=0;i<relist.size();i++){
            res[i] = relist.get(i);
        }
        System.out.println(relist);

        return res;
    }

    public int recursion(boolean[] isUsed,int[] nums1, int[] nums2, List<Integer> list, int recordNum){
        if(list.size()>=nums1.length){
//            relistALL.add(new ArrayList(list));
            int recordNow = judge(list, nums2);
            if(recordNow>recordNum){
                relist = new ArrayList(list);
                recordNum = recordNow;
            }
            return recordNum;
        }

        for(int i=0;i<nums1.length;i++){
            if(!isUsed[i]){
                isUsed[i] = true;
                list.add(nums1[i]);
                recordNum = recursion(isUsed, nums1, nums2, list, recordNum);
                list.remove(list.size()-1);
                isUsed[i] =false;
            }
        }

        return recordNum;
    }

    public int judge(List<Integer> list,int[] nums2){
        int record = 0;
        for(int i=0;i<list.size();i++){
            if(list.get(i)>nums2[i]){
                record++;
            }
        }
        return record;
    }
}

class SolutionDemoOne4 {
    public static void main(String[] args) {
        String str1 = "abcd";
        String str2 ="acdb";
//        str.substring(0,1).equals("123");
        isFlipedString(str1,str2);


    }

    public static boolean isFlipedString(String s1, String s2) {

        if(s1.length()<1&&s2.length()<1)return true;

        if(s1.length()!=s2.length()){
            return false;
        }

        for(int i=0;i<s2.length();i++){
            String tempStr = s1.substring(i+1, s1.length()) + s1.substring(0, i+1);
            if(tempStr.equals(s1)){
                System.out.println();
                return true;
            }
        }
        return false;
    }

}





class SolutionDemoOne3 {

    static List<Double> resList = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        int[] nums = {5,4,3,3,4,5,1,8,9, 99, 100, 0,0};
//        nums.length
        int tempNum = 3;
        int len = nums.length;
        List<Integer> tempList = new ArrayList<>();
        //遍历所有可能;求差值
        boolean[] isUsed = new boolean[len];
        System.out.println(isUsed[0]);
        resursion(isUsed, nums, tempList, tempNum);
        resList = resList.stream().map(s->{
            if(s<0)s = s*-1;
            return s;
        }).sorted().collect(Collectors.toList());
        System.out.println("resList"+resList);
        System.out.println(resList.get(0));
    }

    private static void resursion(boolean[] isUsed, int[] nums, List<Integer> tempList, int tempNum) {
        if(tempList.size()==tempNum){
            List<Integer> curList = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if (!isUsed[i]) {
                    curList.add(nums[i]);
                }
            }
            System.out.print("cur"+curList);
            System.out.print("tempList"+tempList);
            int sum1 = 0;
            for (int i=0;i<tempList.size();i++) {
                sum1 += tempList.get(i);
            }
            List<Double> curList1 = new ArrayList<>();
            curList.stream().forEach(s->{
                curList1.add((double) s);
            });
            curList1.add((double) sum1/tempNum);
            System.out.println(curList1);
            List<Double> curList2 = curList1.stream().sorted().collect(Collectors.toList());
            System.out.println("curList2"+curList2);
            resList.add(curList2.get(curList2.size()-1)-curList2.get(0));

            return;
        }
        for (int b = 0; b < nums.length; b++) {
            if(!isUsed[b]){
                isUsed[b] = true;
                tempList.add(nums[b]);
                resursion(isUsed,nums, tempList, tempNum);
                tempList.remove(tempList.size()-1);
                isUsed[b] = false;
            }
        }


    }
}







class SolutionDemoOne2 {
    public static void main(String[] args) throws Exception {
        System.out.println("sout---start");
        log("start main...");
        new Thread(() -> {
            log("run task...");
        }).start();
        new Thread(() -> {
            log("mid...");
        }).start();
        new Thread(() -> {
            log("print...");
        }).start();
        log("end main.");
        System.out.println("sout---end");
    }

    static void log(String s) {
        System.out.println(Thread.currentThread().getName() + ": " + s);
    }
}



class SolutionDemo{
    private String name;

    public SolutionDemo(String name) {
        this.name = name;
        System.out.println("ABC123");
    }

    public SolutionDemo() {
        super();
        Test();
    }

    public void Test(){
        System.out.println("ABC");
    }

    public String getName(){
        this.name = name;
        return name;
    }
}

class SolutionDemoOne{
    public static void main(String[] args) {
        SolutionDemo solutionDemo = new SolutionDemo();
        solutionDemo.Test();
        System.out.println(solutionDemo.getName());

        SolutionDemo solutionDemo1 = new SolutionDemo("ZHS");
        System.out.println(solutionDemo1.getName());
    }

    private void canTransform(String start, String end) {
    }
}


class SolutionMainThree1 {
    public static void main(String[] args) {
        int x =4, y = 6;
        x++;
        System.out.println(x);
        System.out.println(++y);
        int res = x++ * 2 * 3 - y/(y%x) + ++y;
//         res = x * 2 * 3 + 1 - y/(y%x) + ++y;
        System.out.println(res);
    }
}



class DemoOfGenericChanged{

    public static void main(String[] args) {
        int sum = sum(1, 2, 3, 4, 5);
        System.out.println(sum);
        int sumF = sumF("SUM",-5, 1, 2, 3, 4, 5);
        System.out.println(sumF);
    }

    public static int sum(int... a){
        int sum = 0;
        for(int i:a){
            sum += i;
        }
        return sum;
    }


    public static int sumF(String s, int b, int... a){
        int sum = 0;
        sum += b;
        for(int i:a){
            sum += i;
        }
//        System.out.println(s + sum);
        return sum;
    }

}







class DemoOfGeneric{

    public static void main(String[] args) {
        List<?> list1 = new ArrayList<Object>();
        List<?> list2 = new ArrayList<Number>();
        List<?> list3 = new ArrayList<Integer>();
        System.out.println("----------");

        //这里的extends是类型通配符上限，最高权限就是Number, 继承了Object
//        List<? extends Number> exList1 = new ArrayList<Object>();
        List<? extends Number> exList2 = new ArrayList<Number>();
        List<? extends Number> exList3 = new ArrayList<Integer>();

        //这里的super是类型通配符下限，最高权限就是Number, 继承了Object
        List<? super Number> suList1 = new ArrayList<Number>();
        List<? super Number> suList2 = new ArrayList<Object>();
//        List<? super Number> suList3 = new ArrayList<Integer>();

    }

}

class GenericDD<T> {
    private T t;

    public T getT() {
        return t;
    }

    public void setT(T t) {
        this.t = t;
    }
}



class GenericDemo{
    public static void main(String[] args) {
        GenericDD<String> generic1 = new GenericDD<String>();
        generic1.setT("AAA");
        System.out.println(generic1.getT());
        GenericDD<Integer> generic2 = new GenericDD<Integer>();
        generic2.setT(123);
        System.out.println(generic2.getT());
        GenericDD<Character> generic3 = new GenericDD<Character>();
        generic3.setT('@');
        System.out.println(generic3.getT());


/*        GenericSampleEn g = new GenericSampleEn();
        g.show("abc");
        g.show(123);
        g.show(false);
        g.show('!');*/

    }

}


class GenericSample<T> {

    public void show(T t){
        System.out.println(t);
    }
}

//泛型改进
class GenericSampleEn {

    public <T> void show(T t){
        System.out.println(t);
    }
}



interface generic<T>{
    public void show(T t);
}

class genericShow<T> implements generic<T>{

    @Override
    public void show(T t) {
        System.out.println(t);
    }
}

class showGenericDemo{
    public static void main(String[] args) {
        generic genericShow = new genericShow();
        genericShow.show(123);
        genericShow.show("aaa");
    }
}

class SolutionMainThree2 {
    //泛型让其接受不同的参数类型
    public static void main(String[] args) {
        Collection c = new ArrayList();
        c.add("21");
        c.add("21");
        c.add("21");
//        Iterator it = c.iterator();
        Iterator it = c.iterator();
        while(it.hasNext()){
            String s = (String) it.next();
            System.out.println(s);
        }

    }

}


class SolutionMainThree {

    interface Rabit{
        public void bite();
    }

    interface Target{
        public void target(String s);
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();


        Target target = new Target() {
            @Override
            public void target(String s) {
                System.out.println("targetS" + s);
            }
        };
        target.target("a");

        Target target1 = (s)->{
            System.out.println("targetS" + s);
        };
        target.target("abc");

        System.out.println("---------------------------------");

        Rabit rat = new Rabit() {
            @Override
            public void bite() {
                System.out.println("bite people");
            }
        };
        rat.bite();

        Rabit rat1 = ()->{
            System.out.println("bite rite");
        };
        rat1.bite();
    }

}

class SolutionMainTwo {

    interface Fox{
        public  void ff_fdx();
    }

    public static void main(String[] args) {
        Fox fox = new Fox() {
            @Override
            public void ff_fdx() {
                System.out.println("aaa");
            }
        };
        fox.ff_fdx();

        Fox fox1 = () -> {System.out.println("正在吃add");};
        fox1.ff_fdx();
    }

}


class test {
    //此方法调用了IEat接口中的eat方法
    public static void personEat(IEat e)
    {
        e.eat("蔬菜");
    }

    public static void main(String[] args) {
        IEat e = new IEat() {
            @Override
            public void eat(String v) {
                System.out.println("正在吃"+v);
            }
        };
        personEat(e);

        IEat e1 = (String v) -> {System.out.println("正在吃   " + v);};
        personEat(e1);
    }
}
interface IEat
{
    void eat(String v);
}


class SolutionMainOne {

    public static void main(String[] args) {
        int[] nums = {1,-1,0};
        int k = 0;
        SolutionMainOne s = new SolutionMainOne();
        int res = s.subarraySum(nums, k);
        System.out.println(res);

    }

    public int subarraySum(int[] nums, int k) {
        int res = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int temp = k;
            temp -= nums[i];
            int point = i;
            while(true){
                if(temp==0){
                    res++;
                }
                point++;
                if(point>=len){
                    break;
                }
                temp -= nums[point];

            }
        }
        return res;

    }


}



class AwaitSignalExample {
    private Lock lock = new ReentrantLock();
    private Condition condition = lock.newCondition();

    public static void main(String[] args) {
        ExecutorService executorService = Executors.newCachedThreadPool();
        AwaitSignalExample example = new AwaitSignalExample();
        executorService.execute(() -> example.after());
        executorService.execute(() -> example.before());
        executorService.shutdown();
    }

    public void before() {
        lock.lock();
        try {
            condition.signalAll();
            System.out.println("before");
        } catch (Exception e) {
            e.printStackTrace();
        }
        lock.unlock();

    }

    public void after() {
        lock.lock();
        try {
            condition.await();
            System.out.println("after");
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
}


class WaitNotifyExample {

    public static void main(String[] args) {
        ExecutorService executorService = Executors.newCachedThreadPool();
        WaitNotifyExample example = new WaitNotifyExample();
        executorService.execute(()->example.after());
        executorService.execute(()->example.before());
        executorService.shutdown();
    }
    public synchronized void before() {
        this.notifyAll();
        System.out.println("before!");
    }

    public synchronized void after() {
        try {
            this.wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("after!");

    }
}

class JoinExample {

    public static void main(String[] args) {
        JoinExample example = new JoinExample();
        example.test();
    }

    private class A extends Thread {
        @Override
        public void run() {
            System.out.println("A");
        }
    }

    private class B extends Thread {

        private A a;

        B(A a) {
            this.a = a;
        }

        @Override
        public void run() {
            try {
                a.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("B");
        }
    }

    public void test() {
        A a = new A();
        B b = new B(a);
        b.start();
        a.start();
    }

}


class LockExample {

    private Lock lock = new ReentrantLock();


    public static void main(String[] args) {
        LockExample lockExample = new LockExample();
        ExecutorService executorService = Executors.newCachedThreadPool();
        executorService.execute(() -> {
            try {
                lockExample.func();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        executorService.execute(() -> {
            try {
                lockExample.func();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
    }

    public void func() throws InterruptedException {
        this.wait();
        this.notify();
        synchronized (this){
            this.wait();
            this.notify();
        }
        lock.lock();
        try {
            for (int i = 0; i < 10; i++) {
                System.out.print(i + " ");
            }
        } finally {
            lock.unlock(); // 确保释放锁，从而避免发生死锁。
        }
    }
}

class SynchronizedExample {
    static Object object = new Object();

    public static void main(String[] args) {
        SynchronizedExample e1 = new SynchronizedExample();
        SynchronizedExample e2 = new SynchronizedExample();
        ExecutorService executorService = Executors.newCachedThreadPool();
        executorService.execute(() -> e1.func1());
        executorService.execute(() -> e2.func1());
        executorService.shutdown();
    }

    public void func1() {
        synchronized (SynchronizedExample.class) {
            for (int i = 0; i < 10; i++) {
                System.out.println(Thread.currentThread().getName() + ": " +  i + " ");
            }
        }
    }

    public synchronized void func2() {

            for (int i = 0; i < 10; i++) {
                System.out.println(Thread.currentThread().getName() + ": " +  i + " ");
            }

    }
}


class InterruptExample1 {


    public static void main(String[] args) {
        ExecutorService executorService = Executors.newCachedThreadPool();
        executorService.execute(() -> {
            try {
                Thread.sleep(2000);
                System.out.println("Thread run");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        executorService.shutdownNow();
        System.out.println("Main run");
    }
}

class InterruptExample {

    private static class MyThread1 extends Thread {
        @Override
        public void run() {
            try {
                Thread.sleep(2000);
                System.out.println("Thread run");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread thread1 = new MyThread1();
        thread1.start();
        thread1.interrupt();
        System.out.println("Main run");
    }

}


class MMM{
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        minNumber(nums);
    }

    static List<String> resList = new ArrayList<>();
    public static String minNumber(int[] nums) {

        List<String> list = new ArrayList<>();
        Arrays.stream(nums).forEach(s->list.add(String.valueOf(s)));
        int len = list.size();
        boolean[] isUsed = new boolean[len];
        recursion(nums, 0, len, isUsed, "");
        System.out.println(resList);
        List<Integer> collect = resList.stream().distinct().map(s -> Integer.valueOf(s)).sorted().collect(Collectors.toList());
        System.out.println(collect.size());
        int result = collect.get(0);
        System.out.println(collect.get(0));
        return String.valueOf(result);
    }

    private static void recursion(int[] nums, int depth, int len, boolean[] isUsed, String res) {
        if(depth>=len){
            resList.add(res);
            return;
        }
        for (int i = 0; i < len; i++) {
            if(!isUsed[i]){
                isUsed[i]=true;
                recursion(nums, depth+1, len, isUsed, res + nums[i]);
                isUsed[i] = false;
            }
        }
    }

}




class MM{

    public static void main(String[] args) {
        int[] nums = {2,0,2,1,1,0,3,4,3};
        sortColors(nums);
        String s = Arrays.toString(nums);
        System.out.println(s);
//        nums);
    }
    public static void sortColors(int[] nums) {
        //0  1  2
        int start = 0;
        int len = nums.length;
        recursion(start, len, nums);

    }

    private static void recursion(int start, int len, int[] nums) {

        if(start>=len){
            return;
        }
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]>nums[i+1]){
                int temp = nums[i];
                nums[i] = nums[i+1];
                nums[i+1] = temp;
            }
        }
        recursion(start+1, len, nums);
    }


}

//如果是ASAFASAFADDD，每四个必须出现ASDF, 返回最小需要修改的子串；
//ASAFASAFADDD
//


class MainOOOQA {
    public static void main(String[] args) {
        String str = "ASAFASAFADDD";
        StringBuilder str0 = new StringBuilder();
        int num = str.length()/4-1;
        while(num>=0){
            str0.append("ASDF");
            num--;
        }
        String str1 = str0.toString();
        System.out.println("str"+str);
        System.out.println("str1"+str1);
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < str.length(); i++) {
            if(!str.substring(i,i+1).equals(str1.substring(i,i+1))){
                list.add(i);
            }
        }
        list.sort((a,b)->a-b);
        int res = 0;
        if(list.size()==0) res = 0;
        else if(list.size()==1)res=1;
        else  {
            res = list.get(list.size()-1)-list.get(0);
        }
        System.out.println(list);
        System.out.println(res);
    }
}



class MainOOO{
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        List<String> list = new ArrayList<>();
        while(in.hasNext()){
            list.add(in.next());
        }
        System.out.println(list);
    }
}



class MainOOOA{
    public static void main(String[] args) {
        String name = "0101011101";
        List<Integer> list = new ArrayList<>();

        int res = 0;
        for (int i = 0; i < name.length()-1; i++) {
            int maxLen = 1;
            for (int j = i; j < name.length()-1; j++) {
                String temp = name.substring(j,j+1);
                if(temp.equals(name.substring(j+1,j+2))){
                    break;
                }else{
                    maxLen++;
                }
                res = Math.max(res, maxLen);
            }

        }
        System.out.println(res);
    }
}


class SolutionABCDINt {
    public static void main(String[] args) {
        double a = 1.98;
        double b = 1.18;

        int[][] points = {  {3,1},
                            {2,4}  };
        int maxX = -1;
        int maxY = -1;
        for (int i = 0; i < points.length; i++) {
            maxX = Math.max(maxX, points[i][0]);
            maxY = Math.max(maxY, points[i][1]);
        }
        int min = Math.min(maxX, maxY);
        int max = Math.max(maxX, maxY);
        int res = min*2 + max;

        System.out.println(maxX);
        System.out.println(maxY);
        System.out.println(res);
    }
}




class SolutionABCD {

    static List<List<String>> reslist = new ArrayList<>();
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(1);
        queue.offer(1);
        Deque<Integer> deque = new ArrayDeque<>();
        deque.poll();

        deque.isEmpty();
        deque.add(1);
        deque.add(2);
        deque.add(3);



        List<String> list = new ArrayList<>();
        String a = "30,60,5,7";
        String b = "18,20,6,8";
        String[] splitA = initA(a);
        String[] splitB = initB(b);

        int sum = 0;
        int min = Integer.MAX_VALUE;
        int len = splitA.length;
        dfs(list, len, splitA, splitB, 0);

        min = computer(sum, min);
        System.out.println(min);
        System.out.println(reslist);
    }

    private static String[] initA(String num){
        String[] split = num.split(",");
        for (int i = 0; i < split.length; i++) {
            split[i] = "A" + split[i];
        }
        return split;
    }

    private static String[] initB(String num){
        String[] split = num.split(",");
        for (int i = 0; i < split.length; i++) {
            split[i] = "B" + split[i];
        }
        return split;
    }

    private static int computer(int sum, int min){
        for (int i = 0; i < reslist.size(); i++) {
            sum = 0;
            List<String> res = reslist.get(i);
            List<Integer> resA = new ArrayList<>();
            List<Integer> resB = new ArrayList<>();
            for (int j = 0; j < res.size(); j++) {
                String temp = res.get(j);
                int length = temp.length();
                if (temp.substring(0, 1) .equals("A") ) {
                    resA.add(Integer.valueOf(temp.substring(1, length)));
                }
                if (temp.substring(0, 1) .equals("B")) {
                    resB.add(Integer.valueOf(temp.substring(1, length)));
                }
            }

            // 计算A
            if(resA.size()>=3){
                for (int k = 0; k < resA.size(); k++) {
                    sum += resA.get(k);
                }
                sum = (int) (sum * 0.6);
            }else {
                for (int k = 0; k < resA.size(); k++) {
                    sum += resA.get(k);
                }
            }
            // 计算B，算出B是3的几次方来免去最后几个
            int timeB = resB.size() / 3;
            if(timeB>=1){
                for (int k = 0; k < resB.size()-timeB; k++) {
                    sum += resB.get(k);
                }
            }else {
                for (int k = 0; k < resB.size(); k++) {
                    sum += resB.get(k);
                }
            }
            min = Math.min(min, sum);
        }
        return min;
    }

    private static void dfs(List<String> list, int len, String[] splitA, String[] splitB, int step) {
        if(step==len){
            reslist.add(new ArrayList<>(list));
            return;
        }
        list.add(splitA[step]);
        dfs(list, len, splitA, splitB, step+1);
        list.remove(list.size()-1);
        list.add(splitB[step]);
        dfs(list, len, splitA, splitB, step+1);
        list.remove(list.size()-1);
    }
}






class SolutionABC1 {

    public static void main(String[] args) {
        SolutionABC1 solutionABC = new SolutionABC1();
        int[] nums = {1,1,1,2,2,3,4,4,4, 5,5,5,5};
        int k = 2;
        solutionABC.topKFrequent(nums,k);
    }
    public void topKFrequent(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();

        for( int i:nums)list.add(i);

        Map<Integer, Long> collect = list.stream().collect(Collectors.groupingBy(s -> s, Collectors.counting()));
        System.out.println(collect);
        Set<Integer> set = collect.keySet();
        List<Integer> reslist1 = new ArrayList<>();
        for(int i:set){
            reslist1.add(i);
        }
        List<Integer> reslist = new ArrayList<>();
        int[] res = new int[list.size()] ;
        while(!reslist1.isEmpty()){
            int max = Integer.MIN_VALUE;
            int maxRecord = 0;
            for (int i = 0; i < reslist1.size(); i++) {
                if(collect.get(reslist1.get(i))>max){
                    maxRecord = i;
                    max = Math.toIntExact(collect.get(reslist1.get(i)));
                }
            }
            reslist.add(reslist1.get(maxRecord));
            reslist1.remove(maxRecord);
        }
        System.out.println(reslist);

    }
}


class treeDepth2 {


    private static Object object = new treeDepth2();
    static UserHead userHead = new UserHead();

    public static void main(String[] args) {

        for (int i = 0; i < 10; i++) {
            new Thread(()->{
                userHead.change();
            }, "Id_" + i ).start();
        }

        System.out.println(userHead.getNum());
    }
}

@Data
class UserHead{
    private String name;
    private int num = 0;
    static UserHead userHead = new UserHead();

    public static void main(String[] args) throws InterruptedException {
        synchronized (userHead){
            for (int i = 0; i < 10; i++) {
                new Thread(()->{
                    userHead.change();
                }, "Id_" + i ).start();
            }
        }


        System.out.println(userHead.getNum());
    }

    public synchronized void change(){

            num++;

    }


}

class treeDepth1{

    private static  Object object = new Object();
    private static  Object object1 = new treeDepth1();
    private static  Object object2 = new LowerLayerSourceCode.User();


    public static void main(String[] args) {
        synchronized (object1) {
            System.out.println(object.getClass());
            System.out.println(object.toString());

            System.out.println(object1.getClass());
            System.out.println(object1.toString());

            System.out.println(object2.getClass());
            System.out.println(object2.toString());
        }
    }




}

class treeDepth{

    private static  Object object = new Object();
    public static void main(String[] args) {
        synchronized (object){

        }
        Map map = new HashMap();
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.right = new Node(3);
        root.left.left = new Node(1);
        root.left.left.left  = new Node(1);
        root.left.left.left.left = new Node(1);
        treeDepth node = new treeDepth();
        List<Integer> list = new ArrayList<>();
        if(root==null) System.out.println(0);
        else{
            node.dfs(root, 0, list);
            list.sort((a,b)->b-a);
            System.out.println(list.get(0));
        }

    }

    private void dfs(Node root, int depth, List<Integer> list) {
        if(root == null){
            list.add(depth);
            return;
        }
        depth++;
        dfs(root.left, depth, list);
        dfs(root.right, depth, list);
    }
}


class cat {
    static {
        System.out.println("static cat");
    }
    public cat() {
        super();
    }
}

class catKing extends cat {
    static {
        System.out.println("static catKing");
    }
    public catKing() {
        super();
//        System.out.println("create catKing");
    }
}

class catWorld{
    public static void main(String[] args) {
        cat cat = new cat();
//        catKing catKing = new catKing();
    }
}


class StaticCode {
    public static int count = 0;
    {
        count++;
        System.out.println("非静态代码块 count=" + count);
    }
    static {
        count++;
        System.out.println("静态代码块1 count=" + count);
    }
    static {
        count++;
        System.out.println("静态代码块2 count=" + count);
    }
    public static <T> void main(String[] args) {
        Map<T, T> map =  new ConcurrentHashMap<>();
        Map<T, T> map1 =  new Hashtable<>();
        System.out.println("*************** StaticCode1 执行 ***************");
        StaticCode sct1 = new StaticCode();
        System.out.println("*************** StaticCode2 执行 ***************");
        StaticCode sct2 = new StaticCode();
    }
}



class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};



class SolutionNode {
    Stack<Node> stack = new Stack<>();

    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.right = new Node(3);
        root.left.left = new Node(1);
        SolutionNode node = new SolutionNode();
        node.treeToDoublyList(root);
    }
    public Node treeToDoublyList(Node root) {


        dfs(root);

        Node res = stack.pop();
        Node temp = res;
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            temp.left = cur;
            cur.right = temp;
            temp = cur;
        }
        System.out.println(res.val);
        System.out.println(res.left.val);
        System.out.println(res.left.left.val);
        System.out.println(res.left.left.left.val);
        System.out.println(res.left.left.left.left.val);

        return res;
    }
    public void dfs(Node node) {
        if(node==null)return;
        dfs(node.left);
        stack.push(node);
        dfs(node.right);
    }

}
class Solution {
    public ArrayList<Node> s = new ArrayList<>();

    public Node treeToDoublyList(Node root) {
        if (root == null)
            return null;
        dfs(root);
        int n = s.size();
        Node pre = s.get(n - 1);
        for (int i = 0; i < n - 1; ++i) {
            Node cur = s.get(i);
            cur.left = pre;
            cur.right = s.get(i + 1);
            pre = cur;
        }
        Node cur = s.get(n - 1);
        cur.left = pre;
        cur.right = s.get(0);
        return s.get(0);
    }

    public void dfs(Node root) {
        if (root != null) {
            dfs(root.left);
            s.add(root);
            dfs(root.right);
        }
    }
}




class FindStr{
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<>();

        String[][] board = {{"A"},{"A"}};

        String[][] board3 = {{"A","B","C","E"},
                            {"S","F","C","S"},
                            {"A","D","E","E"}};

        String[][] board2 = {{"A","B","C","E"},
                            {"S","F","C","S"},
                            {"A","D","E","E"}};
        String[][] board1 = {{"A","B","C","E"},
                            {"S","F","C","S"},
                            {"A","D","E","E"}};
        String word = "A";
//        String word = "ABCCED";
        //dfs遍历去递归所有的可能;
        //先找到头部，进而去做后面的操作;
        //这里其实也是一个isUsed，如果用过，就不可以使用，就是一个多叉树;
        int len = board.length;
        int length = board[0].length;
        String head = word.substring(0,1);

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < length; j++) {
                if(board[i][j].equals(head)){
                    boolean[][] isUsed = new boolean[len][length];
                    isUsed[i][j] = true;
                    dfs(isUsed, len, length, board, word, i, j, head, 0);
                }
            }
        }
        if(list.contains(1)) System.out.println("okk");
    }

    private static void dfs(boolean[][] isUsed, int len, int length, String[][] board, String word, int i, int j, String res, int step) {
        if(i>=len||j>=length)return;
        if(step<word.length()){
            String temp = word.substring(0,step+1);
            if(!temp.equals(res)) return;
        }else return;

        if(res.equals(word)) {
            list.add(1);
            return;
        }
        String arr = Arrays.toString(isUsed);
        System.out.println(arr);
        //东西南北走试试，递归走
        if(i>=0&&j+1<length&&isUsed[i][j+1]==false){
            isUsed[i][j+1] = true;
            dfs(isUsed, len, length, board, word, i, j+1, res+board[i][j+1], step+1);
            isUsed[i][j+1] = false;
        }
        if(i>=0&&j>=0&&i+1<len&&j<length&&isUsed[i+1][j]==false){
            isUsed[i+1][j] = true;
            dfs(isUsed, len, length, board, word, i+1, j, res+board[i+1][j], step+1);
            isUsed[i+1][j] = false;
        }
        if(i-1>=0&&j>=0&&i-1<len&&j<length&&isUsed[i-1][j]==false){
            isUsed[i-1][j] = true;
            dfs(isUsed, len, length, board, word, i-1, j, res+board[i-1][j], step+1);
            isUsed[i-1][j] = false;
        }
        if(i>=0&&j-1>=0&&i<len&&j-1<length&&isUsed[i][j-1]==false){
            isUsed[i][j-1] = true;
            dfs(isUsed, len, length, board, word, i, j-1, res+board[i][j-1], step+1);
            isUsed[i][j-1] = false;
        }
    }
}


class PrintABCUsingLock {

    private int times; // 控制打印次数
    private int state;   // 当前状态值：保证三个线程之间交替打印
    private Lock lock = new ReentrantLock();

    public PrintABCUsingLock(int times) {
        this.times = times;
    }

    private void printLetter(String name, int targetNum) {

        for (int i = 0; i  < this.times;){
            lock.lock();
            if (state % 3 == targetNum) {
                state++;
                i++;
                System.out.print(name);
            }
            lock.unlock();
        }
    }

    public static void main(String[] args) {

        //顺序打印10次
        PrintABCUsingLock loopThread = new PrintABCUsingLock(10);

        new Thread(() -> {
            loopThread.printLetter("A", 0);
        }, "A").start();

        new Thread(() -> {
            loopThread.printLetter("B", 1);
        }, "B").start();

        new Thread(() -> {
            loopThread.printLetter("C", 2);
        }, "C").start();
    }

}



class PrintABCUsingWaitNotify {

    private int state;
    private int times;
    private static final Object LOCK = new Object();

    public PrintABCUsingWaitNotify(int times) {
        this.times = times;
    }

    private void printLetter(String name, int targetState) {
        for (int i = 0; i < times; i++)
            synchronized (LOCK) {
                while (state % 3 != targetState) {
                    try {
                        LOCK.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                state++;
                System.out.print(name);
                LOCK.notifyAll();
            }
    }

    public static void main(String[] args) {

        PrintABCUsingWaitNotify printABC = new PrintABCUsingWaitNotify(10);
        new Thread(() -> {
            printABC.printLetter("A", 0);
        }, "A").start();
        new Thread(() -> {
            printABC.printLetter("B", 1);
        }, "B").start();
        new Thread(() -> {
            printABC.printLetter("C", 2);
        }, "C").start();
    }

}


class ThreadWe1{
    private Object LOCK = new Object();
    private int num;
    private int state;
    public static void main(String[] args) throws InterruptedException {
        ThreadOne a = new ThreadOne();

        new Thread(() -> {

            try {
                a.printNum(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        }, "1").start();
        new Thread(() -> {
            try {
                a.printNum(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "2").start();

        new Thread(() -> {
            try {
                a.printNum(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "3").start();

        new Thread(() -> {

            try {
                a.printNum(4);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        }, "4").start();

    }


    public void printNum(int num) throws InterruptedException {

        for (int i = 0; i < 10; i++) {
            synchronized (LOCK){
                while(state % 4 != num ){
                    try {
                        LOCK.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                state++;
                System.out.println(Thread.currentThread().getName());
                LOCK.notifyAll();
            }
        }
    }

}


class ThreadWe{
    private Object LOCK = new Object();
    private int num;

    public static void main(String[] args) throws InterruptedException {
        ThreadOne a = new ThreadOne();

        Thread thread1 = new Thread(() -> {
            try {
                a.printNum(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "1");
        Thread thread2 = new Thread(() -> {
            try {
                a.printNum(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "2");

        Thread thread3 = new Thread(() -> {
            try {
                a.printNum(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "3");

        Thread thread4 = new Thread(() -> {
            try {
                a.printNum(4);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "4");

        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();

    }


    public void printNum(int num) throws InterruptedException {

        for (int i = 0; i < 100; i++) {
                synchronized (LOCK){
                while(num%4!=i){
                    try {
                        LOCK.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                num++;
                System.out.println(Thread.currentThread().getName());
                LOCK.notifyAll();
            }
        }
    }

}

class ThreadWeOne{
    private Object LOCK = new Object();
    private int num;

    public static void main(String[] args) {
        ThreadWeOne a = new ThreadWeOne();
//        for (int i = 0; i < 10; i++) {
            a.Method("1");
            a.Method("2");
            a.Method("3");
            a.Method("4");
//        }

    }
    public void Method(String name){
        ThreadOne a = new ThreadOne();
        new Thread(()->{
            try {
                a.printNum(4);
                LOCK.wait(200);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, name).start();
    }


    public void printNum(int num) throws InterruptedException {
        synchronized (LOCK){
            //对象锁 1%4!=0 , wait
            while(num%4!=0){
                LOCK.wait();
            }
            num++;
            System.out.println(Thread.currentThread().getName());
            LOCK.notifyAll();
        }
    }

}




class SolutionBaiduCaseTwo {

    public static void main(String[] args) {
        String s1 = "        for (int i = 0; i < n; i++) {\n";
        String s2 =      "        if ( a < b ) {\n" ;
        String s3 = "        for (int j = 0; j < n; j++) {";

        StringBuilder str = new StringBuilder();
        List<String> list = new ArrayList<>();
        list.add(s1);
        list.add(s2);
        list.add(s3);
        list.stream().forEach(o->{
            str.append(o);
        });
        String s = str.toString();

        s.contains("for");

        String[] split = s.split("for ()");
        System.out.println(split.length-1);


    }


}
class SolutionBaiduCaseOne {



    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(2, 3, 4, 2, 3, 3,4);
         List<Integer> reslist = new ArrayList<>();
        int[] nums = {1, 1, 2, 3, 2, 3,4};//1 1 2 3 2 3
//        int[] nums = {2, 3, 4, 2, 3};//1 1 2 3 2 3
        int payment = 0;
        int len = nums.length;
        dfs(nums, payment, len, 0, reslist);
        for (int i = 0; i < nums.length; i++) {
            payment += nums[i];
        }
        String s = Arrays.toString(nums);
        System.out.println(reslist);
        System.out.println(s);
        System.out.println(payment +reslist.get(reslist.size()-1));


    }

    private static void dfs(int[] nums, int payment, int len, int point, List<Integer> reslist) {
        if(point==len-3){
            return ;
        }

        for (int i = point; i < nums.length-2; i++) {
            if((nums[i]>=1&&nums[i+1]>=2&&nums[i+2]>=3)){
                payment += 5;
                nums[i] -= 1;
                nums[i+1] -= 2;
                nums[i+2] -= 3;
                reslist.add(payment);
                dfs(nums, payment, len, i, reslist);
                System.out.println("payment"+payment);
            }
        }
    }


}





class SolutionBaiduCase {
    static List<Character> characterList = Arrays.asList('a', 'e','i','o','u');
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        String s = "baid";
        int res = 0;
        if(s.length()<5) System.out.println(0);
        for (int i = 0; i < s.length()-4; i++) {
            String temp = s.substring(i, i+5);
            if(judge(temp))res++;

            System.out.println(temp + ": " + res);
        }

        System.out.println(res);
    }

    private static boolean judge(String temp) {
        char[] chars = temp.toCharArray();

        boolean flag = true;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < chars.length; i++) {
            if(i==0||i==3){
                if(characterList.contains(chars[i]))flag=false;
            }
            if(i==1||i==2||i==4){
                if(!characterList.contains(chars[i]))flag=false;
                if (!set.add(chars[i]))flag=false;
            }
        }
        return flag;
    }

}











class SolutionOneCase {

    private int res;

    public static void main(String[] args) {
        SolutionOneCase solutionCaseOne = new SolutionOneCase();
        int[] prices = {1,2,3,4,5};
        solutionCaseOne.maxProfit(prices);

    }

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        this.res = 0;
        dfs(prices, 0, len, 0, res);
        System.out.println(res);
        return this.res;
    }

    /**
     * @param prices 股价数组
     * @param index  当前是第几天，从 0 开始
     * @param status 0 表示不持有股票，1表示持有股票，
     * @param profit 当前收益
     */
    private void dfs(int[] prices, int index, int len, int status, int profit) {

        if (index == len) {
            this.res = Math.max(this.res, profit);
            return;
        }

        dfs(prices, index + 1, len, status, profit);

        if (status == 0) {
            // 可以尝试转向 1
            dfs(prices, index + 1, len, 1, profit - prices[index]);

        } else {
            // 此时 status == 1，可以尝试转向 0
            dfs(prices, index + 1, len, 0, profit + prices[index]);
        }
    }
}




class SolutionCaseOne {

    private int res;

    public static void main(String[] args) {
        SolutionCaseOne solutionCaseOne = new SolutionCaseOne();
        solutionCaseOne.maxProfit();

    }

    public int maxProfit() {
        int[] prices = {1,2,3,4,5};
        //过去的收益加当前是否 买入/卖出
        this.res = 0;
        int len = prices.length;
        dfs(prices, 0, len, 0, res);
        System.out.println(this.res);
        return res;
    }

    public void dfs(int[] prices, int index, int len, int status, int profit){
        if(index == len){
            res = Math.max(profit, res);
            return;
        }
        //先遍历下所有不买入
        //如果下面买入时，带入当前值，这里就是不做任何操作
        dfs(prices, index+1, len, status, profit);

        if(status==0){
            //买入
            dfs(prices, index+1, len, 1, profit - prices[index]);
        }else{
            //当持有时卖出
            dfs(prices, index+1, len, 0, profit + prices[index]);
        }

    }

}









class MainSolutionTwo {
    public static void main(String[] args) {
        System.out.println(-12 % 5);
        double d = 1.2;
        long l = (long) 1.2;
        System.out.println(l);
        float f = (float) (d/l);
        System.out.println(f);
    }
}


class MainSolutionOne {
    public static void main(String[] args) {

        int a = 2285;
        String curNum = String.valueOf(a);
        int cur = 1;
        int time = 0;
        while(curNum.length()!=1){
            cur = 1;
            for (int i = 0; i < curNum.length(); i++) {
                cur = cur * Integer.valueOf(curNum.substring(i,i+1));
            }
            curNum = String.valueOf(cur);
            time++;
        }
        System.out.println(time);
    }
}





class SolutionCaseT1 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> arr = new ArrayList<>();
    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        SolutionCaseT1 solutionCaseTwo = new SolutionCaseT1();
        solutionCaseTwo.combinationSum(candidates, target);
    }

    private void combinationSum(int[] candidates, int target) {
        if(target < 0) return ;
        if(target==0){
            res.add(new ArrayList<>(arr));
            return ;
        }


    }



}


class SolutionCaseT {



    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7}; int target = 7;
//        int[] candidates = {100,200,4,12};int target = 400 ;


        SolutionCaseT solutionCaseTwo = new SolutionCaseT();
        solutionCaseTwo.combinationSum(candidates, target);
    }


    public void combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> arr = new ArrayList<>();
        int len = candidates.length;
        dsp(res, arr, target, candidates, len, 0);
        res = res.stream().peek(s -> s.sort((a, b) -> a - b)).collect(Collectors.toList());
        res = res.stream().distinct().collect(Collectors.toList());

        System.out.println(res);
    }

    private void dsp(List<List<Integer>> res, List<Integer> arr, int target, int[] candidates, int len
            , int begin) {
        if(target<0)return ;
        if(target==0){
            res.add(new ArrayList<>(arr));
            return ;
        }

        for (int i = begin; i < len; i++) {
            arr.add(candidates[i]);
//            target -= candidates[i];
//            dsp(res, arr, target , candidates, len, begin);
            //为什么替换下就可以了, 是因为target已经变化了，不会返回上一个阶段的值， 比如如果是dsp(a), 到下一个阶段，返回上一个阶段，还是那个阶段的
            //变量，但是如果在外面的话，就不行了，就已经保存在总的空间中了，不会返回

            dsp(res, arr, target - candidates[i], candidates, len, i);
            arr.remove(arr.size()-1);
        }

    }




    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            // 状态重置
            path.removeLast();
        }
    }

}










class SolutionCaseTwo {
    List<List<Integer>> res = new ArrayList<>();
    static List<List<Integer>> res1 = new ArrayList<>();
    public static void main(String[] args) {
        int[] candidates = {2,3,6,7};
        int target = 7;

        SolutionCaseTwo solutionCaseTwo = new SolutionCaseTwo();
        solutionCaseTwo.combinationSum(candidates, target);

        System.out.println(res1);

    }


    public List<List<Integer>> combinationSum(int[] candidates, int target ) {
        int len = candidates.length;

        if (len == 0) {
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        System.out.println(res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param begin      搜索起点
     * @param len        冗余变量，是 candidates 里的属性，可以不传
     * @param target     每减去一个元素，目标值变小
     * @param path       从根结点到叶子结点的路径，是一个栈
     * @param res        结果集列表
     */
    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            // 状态重置
            path.removeLast();
        }
    }
}
















class SolutionOne {
    public void combinationSum() {
        List<List<Integer>> list = new ArrayList<>();
        int[] candidates = {2,3,6,7};
        int target = 7;
        List<Integer> arrList = new ArrayList<>();
        


    }
}





class aabc{
    aabc aabc = new aabc();
    Cat c1 = new Cat("星期五");
    Cat c2 = new Cat("星期五");
    public static void main(String[] args) {
        aabc aabc = new aabc();
        System.out.println();
        aabc.test();

    }

    public void test(){
//        System.out.println(this == aabc.getClass());
        System.out.println(this == aabc);
        System.out.println(this );
        System.out.println(aabc);
    }
}




class Cat {
    public Cat(String name) { this.name = name; }
    private String name; public String getName() { return name; }
    public void setName(String name) { this.name = name; }

    @Override
    public String toString() {
        return "Cat{" +
                "name='" + name + '\'' +
                '}';
    }
}

class testDomeOne1 {
    public static void main(String[] args) {
        Cat c1 = new Cat("星期五");
        Cat c2 = new Cat("星期五");
        System.out.println(c1.toString());
        System.out.println(c2.toString());
        System.out.println(c1.hashCode());
        System.out.println(c2.hashCode());
        System.out.println(c1==c2);
        System.out.println(c1.toString().equals(c2.toString()));
    }
}



class testDomeOne{

    public static void main(String[] args) {
        String s1 = "a" + "b";
        String s2 = new String(s1);
        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());
        if(s1==s2) System.out.println("suuu");

        // ==基本类型：比较的是值是否相同；引用类型：比较的是引用是否相同；


        //==设计的目的就是为比较两个对象是否是同一个对象。
        //比较对象的相等不仅要比较对象内容相等，还要比较对象引用地址是否相等。
        if(s1.equals(s2)) System.out.println("jjjjjj");

        //==比较的是两个对象是否是同一个对象，这并不能满足很多需求。
        // 有时候当两个对象不==的时候，我们仍然会认为两者是“相等”的，
        // 比如对于String对象，当两个对象的字符串序列是一致的，我们就认为他们是“相等”的。
        // 对于这样的需求，需要equals()来实现。记得重写 toString

        System.out.println("-----------");
        String s3 = "es";
        String s4 = "es";
        System.out.println(s3.hashCode());
        System.out.println(s4.hashCode());
        System.out.println(s3==s4);
        System.out.println(s3.equals(s4));
        s3 = "123";
        System.out.println("s3" + s3);
        System.out.println("s4" + s4);
        System.out.println(s3.hashCode());
        System.out.println(s4.hashCode());
        System.out.println(s3==s4);
        System.out.println(s3.equals(s4));
        //hashCode()方法返回的是一个数值，称之为hashCode。hashCode()方法在Object类中的定义如下
        //①若两个对象相等（equals），那么这两个对象一定有相同的哈希值（hashCode）；②若两个对象的哈希值相同，但这两个对象并不一定相等。

        String s5 = "es";
        String s6 = new String("es");
        System.out.println("-----------");
        System.out.println(s5.hashCode());
        System.out.println(s6.hashCode());
        System.out.println(s5==s6);
        System.out.println(s5.equals(s6));


    }
}



class demoStatic{

    public static void main(String[] args) {
        System.out.println("static" + staticCase.sum);
        staticCase staticCase = new staticCase();
        System.out.println(staticCase.noSum);

    }
}

class staticCase{
    public static int sum = 1;
    public int noSum = 2;
    public staticCase(){
        sum = sum + 5;
        noSum += 2;
    }

    public static int getSum() {
        return sum;
    }

    public static void setSum(int sum) {
        staticCase.sum = sum;
    }

    public int getNoSum() {
        return noSum;
    }

    public void setNoSum(int noSum) {
        this.noSum = noSum;
    }
}

class demoStaticOne {
//    public static int sum = 2;
    public static void main(String[] args) {
        demoStaticOne s = new demoStaticOne();
        System.out.println();
    }

}





class Function{
    public static void main(String[] args) {
        Function f = new Function();
        f.findAnagrams();
    }

    public void findAnagrams() {
        List<Integer> list = new ArrayList<>();
        String s = "cbaebabacd";
        String p = "abc";
        char[] arrc = p.toCharArray();
        Arrays.sort(arrc);
        int len = p.length();
        for (int i = 0; i < s.length()-len; i++) {
            char[] chars = s.substring(i, i + len).toCharArray();
            Arrays.sort(chars);
            System.out.println(i + ": " + Arrays.toString(arrc));
            System.out.println(i + ": " + Arrays.toString(chars));
            if(flag(chars, arrc))list.add(i);
        }
        System.out.println(list);

    }

    private boolean flag(char[] chars, char[] arrc) {
        boolean flag = true;
        for (int i = 0; i < chars.length; i++) {
            if(chars[i]!= arrc[i]){
                flag = false;
            }
        }
        return flag;
    }
}


public class Lamdba {

    public static void main(String args[]){
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);

        // Predicate<Integer> predicate = n -> true
        // n 是一个参数传递到 Predicate 接口的 test 方法
        // n 如果存在则 test 方法返回 true

        System.out.println("输出所有数据:");

        // 传递参数 n
        eval(list, n->true);

        // Predicate<Integer> predicate1 = n -> n%2 == 0
        // n 是一个参数传递到 Predicate 接口的 test 方法
        // 如果 n%2 为 0 test 方法返回 true

        System.out.println("输出所有偶数:");
        eval(list, n-> n%2 == 0 );

        // Predicate<Integer> predicate2 = n -> n > 3
        // n 是一个参数传递到 Predicate 接口的 test 方法
        // 如果 n 大于 3 test 方法返回 true

        System.out.println("输出大于 3 的所有数字:");
        eval(list, n-> n > 3 );
    }

    public static void eval(List<Integer> list, Predicate<Integer> predicate) {
        for(Integer n: list) {

            if(predicate.test(n)) {
                System.out.println(n + " ");
            }
        }
    }



    interface L{
        int list(int a, int b);
    }

    public  void main() {
        Lamdba lamdba = new Lamdba();
        L interfacel = (int a, int b)-> {return a+b;};
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("c");
//        list.forEach(System.out::println);
//
//        list.forEach(t->System.out.println(t));
        System.out.println(interfacel.list(5,2));

    }
}







